[BAEKJOON] 9370. 미확인 도착지
Posted on
문제 :
(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)
어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.
이 듀오는 대체 어디로 가고 있는 것일까?
예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.
입력 :
첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다
- 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
- 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
- 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
- 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.
교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.
출력 :
테스트 케이스마다
- 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.
풀이 :
시험기간과 공모전이 계속 겹치면서 알고리즘 공부에 너무 소홀했었다 한동안,,, 그래서 복습하는 차원에서 다익스트라 알고리즘 관련 문제를 풀어보려했다.
처음 접근 당시에는 다익스트라 알고리즘 경로 상에 g→h 혹은 h→g 경로를 포함하면 가능한 경로로 판단하는 코드를 계획하고 코딩했다.
하지만 계속적으로 답이 아니라고 채점되어서 꽤나 고민을 많이 했던 문제이다.
- 우선 다익스트라 알고리즘을 구현할 때 우선순위큐로 구현하는 다익스트라 알고리즘 구현이 가물가물해서 다시금 공부했다.
- 리팩토링 과정에서 다익스트라 코드 부분을 최적화 할 수 있는 방법들을 계속 생각해 보았다. 우선 필요없는 반복과정을 없애기 위해 우선순위 큐에 있는 값을 꺼내 현재 교차로 사이 최단 경로보다 긴 경로를 꺼냈을 경우에는 과정을 생략하도록 구현했다.
- 경로를 살펴보면 문제가 있었다. 최단경로 가중치가 같은 경로가 여러개가 나올 수 있기 때문에 단순히 경로 상에 g와 h교차로를 지나가는지 확인하면 문제에서 예외 케이스가 발생할 수 있었다. 따라서 경로를 확인해 보는 것이 아닌 최단경로 가중치 합을 비교해 보아야 했다.
- start→g 경로와 g→h 경로, h→destination 경로합 or start→h 경로와 h→g 경로, g→destination 경로합 이렇게 두가지 경우 중 하나가 start→destination 경로합과 같으면 그 경로는 가능한 경로로 판단할 수 있었다.
코드에 실수가 있었던 것이 아니라 문제 접근 자체에 문제가 있어서 시간이 많이 걸린 문제였다. 또 그래프 탐색 문제들을 다시금 복습할 필요성을 느낀 문제이기도 하다.
코드 :
코드 보기/접기
#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
#include <algorithm>
#define pii pair<int, int>
#define INF 999999999
using namespace std;
vector<int> candidate;
vector<vector<pii>> adj;
int n;
void initializer() {
candidate.clear();
adj.clear();
adj.resize(n + 1);
}
vector<int> dijkstra(int start) {
priority_queue<pii, vector<pii >, greater<pii>> pq;
vector<int> dist(n + 1, INF);
int i, size, comp, distance, cur, compd, cmpd;
dist[start] = 0;
pq.push(pii(0, start));
while (!pq.empty()) {
distance = pq.top().first;
cur = pq.top().second;
pq.pop();
if (distance > dist[cur]) continue;
size = adj[cur].size();
for (i = 0; i < size; i++) {
comp = adj[cur][i].first;
compd = adj[cur][i].second;
cmpd = distance + compd;
if (dist[comp] > cmpd) {
dist[comp] = cmpd;
pq.push(pii(cmpd, comp));
}
}
}
return dist;
}
void testCase() {
int i, m, t, a, b, d, num, size, start, g, h, comp;
vector<int> ansvec;
cin >> n >> m >> t >> start >> g >> h;
initializer();
while (m--) {
cin >> a >> b >> d;
adj[a].push_back(pii(b, d));
adj[b].push_back(pii(a, d));
}
for (i = 0; i < t; i++) {
cin >> num;
candidate.push_back(num);
}
vector<int> orgdist = dijkstra(start);
vector<int> gdist = dijkstra(g);
vector<int> hdist = dijkstra(h);
for (i = 0; i < t; i++) {
comp = candidate[i];
if (orgdist[comp] == orgdist[g] + gdist[h] + hdist[comp] ||
orgdist[comp] == orgdist[h] + hdist[g] + gdist[comp])
ansvec.push_back(candidate[i]);
}
sort(ansvec.begin(), ansvec.end());
size = ansvec.size();
for (i = 0; i < size; i++)
cout << ansvec[i] << ' ';
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc;
cin >> tc;
while (tc--)
testCase();
return 0;
}